package bintree.leetcode;

//106. 从中序与后序遍历序列构造二叉树

public class Num106_buildTree2 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int[] postorder2 = new int[postorder.length];
        int size=postorder.length;
        for (int i = 0; i < postorder.length; i++) {
            postorder2[i]=postorder[size-1];
            size--;
        }
        return buildTreeHelper(inorder,postorder2,0,postorder2.length);
    }

    private int index=0;
    private TreeNode buildTreeHelper(int[] inorder, int[] postorder2, int left, int right) {
        if(left>right){
            return null;
        }
        if(index == postorder2.length){
            return null;
        }

        TreeNode root=new TreeNode(postorder2[index]);
        index++;
        int post = find(root.val,inorder);
        root.right = buildTreeHelper(inorder,postorder2,0,post-1);
        root.left = buildTreeHelper(inorder,postorder2,post+1,right);
        return root;
    }

    private int find(int val,int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            if(val == inorder[i]){
                return i;
            }
        }
        return -1;
    }
}
